package com.itheima.search;

public class A02_BinarySearchDemo1 {
    public static void main(String[] args) {
        /*二分查找*/
        long l = System.currentTimeMillis();
        //数组
        int[] arr =new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i;
        }
        //要查找的数字
        int num=66666;

        //得到索引
        int index = getIndex3(arr, num);
        System.out.println(index);


        long end = System.currentTimeMillis();
        System.out.println(end - l);
    }
    private static int getIndex3(int[] arr,int num) {
        //斐波那契查找
        //定义变量表示索引
        int min=0;
        int max=arr.length-1;

        //循环
        while(true){
            //判断违法情况
            if(min>max){
                System.out.println("不存在");
                return -1;
            }
            int mid=(int)(min+0.618*(max-min)-1);

            //开始找，mid找，min和max限制范围
            if(arr[mid]==num){
                return mid;
            } else if (num<arr[mid]) {
                //数字在左边，max=mid-1
                max=mid-1;

            } else if (num>arr[mid]) {
                //数字在右边，min=mid+1
                min=mid+1;

            }

        }
    }

    private static int getIndex2(int[] arr,int num) {
        //插值查找
        //定义变量表示索引
        int min=0;
        int max=arr.length-1;

        //循环
        while(true){
            //判断违法情况
            if(min>max){
                System.out.println("不存在");
                return -1;
            }
            int mid=((num-arr[min])/(arr[max]-arr[min]))*(max-min)+min;

            //开始找，mid找，min和max限制范围
            if(arr[mid]==num){
                return mid;
            } else if (num<arr[mid]) {
                //数字在左边，max=mid-1
                max=mid-1;

            } else if (num>arr[mid]) {
                //数字在右边，min=mid+1
                min=mid+1;

            }

        }
    }

    private static int getIndex1(int[] arr,int num) {
        //定义变量表示索引
        int min=0;
        int max=arr.length-1;
        int mid=(min+max)/2;



       //循环
        while(true){
            //判断违法情况
            if(min>max){
                System.out.println("不存在");
                return -1;
            }
            //开始找，mid找，min和max限制范围
            if(arr[mid]==num){
                return mid;
            } else if (num<arr[mid]) {
                //数字在左边，max=mid-1
                max=mid-1;
                mid=(min+max)/2;
            } else if (num>arr[mid]) {
                //数字在右边，min=mid+1
                min=mid+1;
                mid=(min+min)/2;
            }

        }
    }
}
